package LearnDataStructure.d_图结构.c_欧拉回路;

import java.util.Stack;

/**
 * @version: 1.0
 * @Author: wuqiu
 * @date: 2023-07-15 16:44
 * @description: LeetcodeLearnAlgorithm -> LearnDataStructure.d_图结构.例题
 */
/*
欧拉道路和欧拉回路

从无向图中的一个结点出发走出一条道路，每条边恰好经过一次，这样的路线称为欧拉道路
如果一个无向图是连通的，且最多只有两个奇点（度数为奇数），则一定存在欧拉道路。
如果有两个奇点，它们必须是起点和，
如果奇点不存在，可以从任意点出发，最终一定会回到该点，称为欧拉回路
*/
public class d_欧拉回路byDFSand回溯and标记 {
    public static void main(String[] args) {
        d_欧拉回路byDFSand回溯and标记 test = new d_欧拉回路byDFSand回溯and标记();
        test.useFindEulerPath();
    }

    public void useFindEulerPath() {
        int N = 4;
        int[][] graph = {//无向图
               //a  b  c  d
                {0, 1, 2, 1},//a
                {1, 0, 0, 0},//b
                {2, 0, 0, 1},//c
                {1, 0, 1, 0} //d
        };
        int[][] visited = new int[N][N];
        Stack<String> result = new Stack<>();
        boolean flag = judgeEuler(graph, N);
        if (flag) {
            findEulerPath(1,N,graph,visited,result);///先以b为起点
            while (!result.isEmpty()) {
                System.out.println(result.pop());
            }
        } else {
            System.out.println("No EulerPath");
            return;
        }
    }

    public boolean judgeEuler(int[][] graph, int N) {
        int count = 0;
        for (int i = 0; i < N; i++) {
            int num = 0;
            for (int j = 0; j < N; j++) {
                num += graph[i][j];
            }
            if ((num & 1) == 1) {
                count++;
            }
        }
        if (count < 1 || count > 2) {
            return false;
        }
        return true;
    }

    public void findEulerPath(int row, int N, int[][] graph, int[][] visited,Stack<String> result) {
        for (int col = 0; col < N; col++) {
            if (graph[row][col] > 0 && graph[row][col] > visited[row][col]) {
                //进行标记；代表着这条路走了一次
                visited[row][col]++;
                visited[col][row]++;
                //以新节点B为起点，递归寻找
                findEulerPath(col,N,graph,visited,result);
                result.push((char)('A' + row) + " -> " + (char)('A' + col));
            }
        }
    }
}
